package cn.edu.xjtu.work.addOneRowToTree;

import cn.edu.xjtu.Util.TreeNode.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author Hydrion-QLz
 * @date 2022-08-05 19:11
 * @description https://leetcode.cn/problems/add-one-row-to-tree/
 * <p>
 * 623. 在二叉树中增加一行
 * <p>
 * 给定一个二叉树的根 root 和两个整数 val 和 depth ，在给定的深度 depth 处添加一个值为 val 的节点行。
 * <p>
 * 注意，根节点 root 位于深度 1 。
 * <p>
 * 加法规则如下:
 * <p>
 * 给定整数 depth，对于深度为 depth - 1 的每个非空树节点 cur ，创建两个值为 val 的树节点作为 cur 的左子树根和右子树根。
 * cur 原来的左子树应该是新的左子树根的左子树。
 * cur 原来的右子树应该是新的右子树根的右子树。
 * 如果 depth == 1 意味着 depth - 1 根本没有深度，那么创建一个树节点，值 val 作为整个原始树的新根，而原始树就是新根的左子树。
 *  
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/add-one-row-to-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    /**
     * 深度优先遍历
     *
     * @param root
     * @param val
     * @param depth
     * @return
     */
    public TreeNode addOneRow(TreeNode root, int val, int depth) {
        if (depth == 1) {
            TreeNode newRoot = new TreeNode(val, root, null);
            return newRoot;
        }
        helper(root, val, depth, 2);
        return root;
    }

    public void helper(TreeNode root, int val, int depth, int currDepth) {
        if (root == null) {
            return;
        }
        if (depth == currDepth) {
            root.left = new TreeNode(val, root.left, null);
            root.right = new TreeNode(val, null, root.right);
        } else {
            helper(root.left, val, depth, currDepth + 1);
            helper(root.right, val, depth, currDepth + 1);
        }
    }

    /**
     * 广度优先遍历
     *
     * @param root
     * @param val
     * @param depth
     * @return
     */
    public TreeNode addOneRow1(TreeNode root, int val, int depth) {
        if (depth == 1) {
            TreeNode newRoot = new TreeNode(val, root, null);
            return newRoot;
        }
        Deque<TreeNode> queue = new LinkedList<>();
        queue.addLast(root);
        int currDepth = 1;
        while (!queue.isEmpty()) {
            currDepth++;
            int size = queue.size();
            while (size > 0) {
                size--;
                TreeNode node = queue.removeFirst();
                if (currDepth == depth) {
                    // 添加一行
                    node.left = new TreeNode(val, node.left, null);
                    node.right = new TreeNode(val, null, node.right);
                } else {
                    // 把下一行加进去
                    if (node.left != null) {
                        queue.addLast(node.left);
                    }
                    if (node.right != null) {
                        queue.addLast(node.right);
                    }
                }
            }
        }

        return root;
    }
}
